1583. Count Unhappy Friends

Description

image-20210814210934272

image-20210814210946985

Solution

Iterate all potential pair(i,j) to see if they are ranked higher in each preference

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int unhappyFriends(int n, vector<vector<int>>& preferences, vector<vector<int>>& pairs) {
        vector<unordered_map<int,int>> perfers(n);
        unordered_map<int,int> Map;
        int res  = 0;
        for(int j = 0; j < n; j ++){
            for(int i = 0; i < n-1; i++){
                perfers[j][preferences[j][i]] = i;
            }
        }
        for(auto pair: pairs){
            Map[pair[0]] = pair[1];
            Map[pair[1]] = pair[0];
        }
        vector<int> visited(n,0);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){
                if(Map[i] == j)
                    continue;
                if(perfers[i][j] < perfers[i][Map[i]] && perfers[j][i] < perfers[j][Map[j]]){
                    res += visited[i] == 0;
                    res += visited[j] == 0;
                    visited[i] = 1;
                    visited[j] = 1;
                }
            }
        }
        return res;
    }
};